The present invention relates to computer software utility programs, and more specifically to programs in the field of computer aided design (CAD), computer aided manufacturing (CAM), and computer aided engineering (CAE), and in particular the use of such systems for determining the proper physical location of robots and machines in a manufacturing facility.
Robots are used extensively in automated manufacturing processes. Robots can be employed to perform repetitive tasks in a precise and time efficient manner. For example, robots are employed in automobile production lines to apply spot welds to automobile frames, resulting in more precise placement of welds, in a more time efficient manner, than can be accomplished through the use of manual labor. As another example, a robot, located in a workcell and surrounded by other machines, obtains parts from the various peripheral machines in the workcell environment and creates a product by assembling the various parts at a workstation. In a typical manufacturing process, a robot performs a repetitive sequence of point-to-point movements, coming to a stop at each point. For example, the robot will apply a spot weld to an assembly at each programmed stop location. As another example, in an assembly operation, a robot will move from one peripheral machine to the next in an operation sequence dictated by the assembly task being performed.
The productivity of a robot can be improved considerably by minimizing the cycle time for completing an operation sequence. For a given robot, cycle time depends on many parameters, such as the position of the manipulator tool of the robot relative to the task, the sequence in which the points are visited, the maximum velocities and accelerations of the actuators, the relative position of the points, and the configuration of the robotic arm. It also depends on the relative position of the points that the robot will access, and thus on workcell layout. A robot ill-placed at its workstation risks inefficient operation and even failure. Thus, there is a need for a system for choosing robot and peripheral machine positions so that cycle time can be minimized for a specified operation sequence.
Existing CAD systems can be used to model a manufacturing facility including robots. Such CAD systems, when equipped with data detailing the configuration of the robots, and configuration of peripheral equipment in the workcell, are used to model the workplace. Each item can be placed within the workcell for the purpose of modeling the facility, and peripheral machines can then be moved to check for task feasibility and efficiency. However, the design process used so far in industry for designing robot workcells contains some interactive check and change loops that must be performed by the user. Such a process is time-consuming and the quality of the layout depends heavily on the human designer. To come to an integrated design process for workcells, an automatic layout planning tool for optimizing robot and peripheral machine position to achieve a low cycle time is required in CAD/CAM/CAE systems.
Accordingly, the present invention provides a system, method and apparatus for finding, in an efficient manner, the optimal or near-optimal layout of a robotic assembly workcell that consists of a robot and peripheral machines. Optimal layout is defined as the placement of a robot and peripheral machines in the workcell (workspace) that will allow the operation sequence to proceed in a minimum amount of time.
The present invention employs a xe2x80x9cconstructive algorithmxe2x80x9d technique which consists of setting up step-by-step subsets of variables until a complete solution is obtained. The items to be placed in the workcell are, of course, the robot and each of the peripheral machines involved in the operation. According to an aspect of the invention, the workcell layout problem is attacked by first placing a robot and a first peripheral machine within a workcell. A second peripheral machine is then selected for placement in the workcell. According to an aspect of the invention, a modified xe2x80x9csimulated annealingxe2x80x9d method is employed to find a set of locations on the floor of the workcell in which the second peripheral machine may be placed. The modified simulated annealing method finds locations that would result in a minimum amount of time for interaction between the robot and the peripheral machines in the workcell (cycle time).
The modified simulated annealing method of the present invention yields a set of placements for the second peripheral machine which are near optimal. That is, none of the locations found in the search is necessarily the absolute optimum (although one of solutions may be the absolute optimum). Nevertheless, the locations found by the method represent near optimum locations for placement of the peripheral machine. According to the invention, although the modified simulated annealing method may generate many possible placements, only the best locations (in terms of cycle time) are kept for further evaluation. The remainder of the locations generated by the simulated annealing method are removed from consideration. According to a preferred embodiment of the invention, only the five best locations are selected. Thus, the partial layout set for further evaluation would consist of five partial layouts, each of which would have the robot and the first machine in their original locations, and the second peripheral machine at a specific location on the workcell floor.
The modified simulated annealing method is performed for each of the kept partial layouts when a new machine is added. Thus, according to an aspect of the invention, a third peripheral machine is chosen for placement. Each of the partial layouts in the partial layout set is then searched using the modified simulated annealing method of the present invention to find a set of possible placements for the third peripheral machine. For each of the five kept partial layouts, the search process yields set of new partial layouts containing the robot, the first two peripheral machines, and the third machine. Since the search is conducted for each of the five kept partial layouts, a large number of layouts containing the third peripheral machine are generated. However, according to an aspect of the invention, again, only the best partial layouts are selected for further evaluation, and the remainder are removed from consideration. According to the preferred embodiment of the invention, only the five best partial layouts are selected, although is to be understood that any number of partial layouts may be selected, as desired by the user or dictated by the availability of CPU time.
The foregoing process is repeated until all of the peripheral machines have been placed in the workcell environment.
According to another aspect of the invention, the first peripheral machine is placed in the center of an xe2x80x9cacceptable base location domainxe2x80x9d. Because of the kinematic limitations of the arm and wrist joints of a robot, the manipulator tool of a robot can only reach a limited amount of discrete locations in its environment for any single robot base location. Likewise, if the manipulator tool of the robot is fixed in one location and the robot base is allowed to move, moving the robot arm and wrist through its operating range will move the base of the robot around the floor of the workcell. The area on the workcell floor in which the robot base travels when the robot is moved through its entire operating range defines the acceptable base location domain of the robot for a particular work point. Placing the robot outside the acceptable base location domain will not allow the robot to reach the work point.
According to another aspect of the invention, the order in which the peripheral machines are evaluated is determined by use of a machine selection rule, which favors as a first criterion machines that are accessed most during the operation sequence, and favors as a second criterion small machines. This results in an improved optimization of cycle time.
According to another aspect of the invention, the shapes of peripheral machines are simplified prior to the application of the simulated annealing method. This results in speeding the process time for the search.
As stated, a modified xe2x80x9csimulated annealingxe2x80x9d method is employed to find a set of optimal positions for peripheral machine placement for minimum cycle time. The classic simulated annealing algorithm will be familiar to a person of skill in the art, and is described, for example, at S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, xe2x80x9cOptimization by Simulated Annealingxe2x80x9d, Science, 220 (4598), pp. 671-680, May 1983, which is incorporated herein by reference. The conventional simulated annealing algorithm can only yield a single and isolated optimal solution to the problem, which is not satisfactory in the context of an industrial CAD system. Furthermore, simulated annealing may require long computation times, as it cannot distinguish a local minimum from an ordinary solution, unless it visits the very bottom of the local minimum. According to the invention, two features were added to the conventional simulated annealing method to build some xe2x80x9copportunismxe2x80x9d into the method.
The first feature is the use of what has been termed a xe2x80x9cfreeze-heatxe2x80x9d cycle, which corresponds to regular application of local search procedures. This feature is aimed at exploring a minimum valley as fast as possible and yields the closest local minimum in the search space. The second feature is the memorization of the local minima and their xe2x80x9cattraction areasxe2x80x9d. In this way a minimum valley is not revisited once it has been explored, and other minima can be obtained. Such modifications yield a set of near-optimal solutions at the end of execution, together with the knowledge of their respective neighborhoods. Using this modification, there is no guarantee that the single absolute optimal location for the robot base will be found. Instead, a set of near-optimal solutions will be obtained, using substantially less computational resources than would be necessary using a classic simulated annealing method.